home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000123_icon-group-sender _Fri Jun 4 08:03:30 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id IAA19581
  4.     for icon-group-addresses; Fri, 4 Jun 1999 08:03:22 -0700 (MST)
  5. Message-Id: <199906041503.IAA19581@baskerville.CS.Arizona.EDU>
  6. Delivered-To: icon-group@silliac.cs.arizona.edu
  7. Date: Fri, 4 Jun 99 00:51:50 -0500 (CDT)
  8. From: gep2@terabites.com
  9. Subject: Find the longest matching substrings
  10. To: icon-group@optima.CS.Arizona.EDU
  11. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  12. Status: RO
  13.  
  14. > I am working on a project that will mark the inserted or deleted phases
  15. between two strings.  I am wondering whether you know any library
  16. procedure that will anchor ( or report ) the longest phases that exists
  17. in both  strings.  
  18.  
  19. I'm not aware of any such ready-made routine, although certainly "longest common 
  20. substring" logic is frequently (and heavily!) used in file compression software 
  21. (PKZIP for example).
  22.  
  23. > For example, assume that we have two strings:
  24.     old:="other strings ab cd e and more substrings"
  25.     new:="some more substrings ab cd ab cd e"
  26.  
  27. > This function should return phases and position in both strings, i.e.
  28. [15,  28, "ab cd e"]  for "ab cd e" is the longest phase that matched (
  29. it has three continuous matching elements ).
  30.  
  31. Intriguing that you consider the "three matching elements" phrase (only seven 
  32. characters) 'longer' than the sixteen-character common phrase " more 
  33. substrings".  I guess the criteria here could be most anything you want to make 
  34. it, but still...  :-)
  35.  
  36. Generally the logic to do stuff like this (in good programs, anyhow) is coded at 
  37. very low levels using very heavily optimized code... since it tends to be very, 
  38. very compute-intensive (this is especially true as the two strings get longer).
  39.  
  40. Of course, the problem's solution might be VERY different depending on whether 
  41. you're looking for something that's "elegant" in terms of the source code, 
  42. versus something that's FAST, versus something that is storage-efficient, or 
  43. something else.  (The rule about what substring is 'longer' also is going to 
  44. have an effect too!).
  45.  
  46. If I were going to try to make something like this FAST (and especially if one 
  47. of the strings were relatively constant) I'd probably want to use a hash (or 
  48. even direct index?) table pre-computed with the offsets of character substrings 
  49. (I'd probably use two-character adjacent pairs) in one of those strings;  this 
  50. would enable stepping rapidly through the second string and quickly finding at 
  51. least (only just the) plausible candidates for launching more detailed substring 
  52. compare (and length computation) operations.  This kind of thing would likely be 
  53. storage-hungry, but that's less of a concern today than it once was.
  54.  
  55. Gordon Peterson
  56. http://web2.airmail.net/gep2/
  57. Support the Anti-SPAM Amendment!  Join at http://www.cauce.org/
  58. 12/19/98: the day the Conservatives demonstrated their scorn for their
  59.    fraudulent sham of representative government.  Voters, remember it!
  60.  
  61.